\begin{Maratona}
    {Maratona de Programação da UFCG/UFMG 2008}
    {05 de Novembro de 2008}{6}

    \Organizacao{
	Eduardo Colaço (UFMG) \\
	Jemerson Damásio (UFCG) \\
	Jonhnny Weslley (UFCG) \\
	Leonardo de Assis (UFCG) \\
	Rohit Gheyi (UFCG)
	}
\end{Maratona}


\begin{Problema}{Best Compression Ever}

Being educated in Computer Science and Mathematics is not always easy. 
Especially not if you have "friends" who repeatedly insist on showing you their 
new "proofs" that $P$ equals $NP$, that the Riemann Hypothesis is true, and so 
on.

One of your friends recently claims to have found a fantastic new compression 
algorithm. As an example of its amazing performance, your friend has told you 
that every file in your precious collection of random bit strings after 
compression would be at most b bits long! Naturally, you find this a bit hard 
to believe, so you want to determine whether it is even theoretically possible 
for this to be true.

Your collection of random bit strings consists of $N$ files, no two of which 
are identical, and each of which is exactly 1000 bits long.

\Entrada

The input consists of two integers $N (1 \leq N \leq 1015 )$ and $b (0 \leq b 
\leq 50)$, giving the number of files in your collection and the maximum number 
of bits a compressed file is allowed to have.

\Saida

Output a line containing either "yes" if it is possible to compress all the $N$ 
files in your collection into files of size at most $b$ bits, or "no" otherwise.
\\

\begin{Exemplo}
\texttt{13 3             }   & \texttt{yes} \\
\texttt{1 0              }   & \texttt{yes} \\
\texttt{31415926535897 40}   & \texttt{no} \\
\end{Exemplo}

\end{Problema}


\begin{Problema}{Event Planning}
As you didn't show up to the yearly general meeting of the Nordic Club of Pin 
Collectors, you were unanimously elected to organize this years excursion to 
Pin City. You are free to choose from a number of weekends this autumn, and 
have to find a suitable hotel to stay at, preferably as cheap as possible.

You have some constraints: The total cost of the trip must be within budget, of 
course. All participants must stay at the same hotel, to avoid last years 
catastrophe, where some members got lost in the city, never being seen again.

\Entrada

The first line of input consists of four integers: $1 \leq N \leq 200$, the 
number of participants, $1 \leq B \leq 500000$, the budget, $1 \leq H \leq 18$, 
the number of hotels to consider, and $1 \leq W \leq 13$, the number of weeks 
you can choose between. Then follow two lines for each of the $H$ hotels. The 
first gives $1 \leq p \leq 10000$, the price for one person staying the weekend 
at the hotel. The second contains $W$ integers, $0 \leq a \leq 1000$, giving 
the number of available beds for each weekend at the hotel.

\Saida

Output the minimum cost of the stay for your group, or "stay home" if nothing 
can be found within the budget. \\

\begin{Exemplo}
\texttt{3 1000 2 3      }  & \texttt{900      } \\
\texttt{200             }  & \texttt{stay home} \\
\texttt{0 2 2           }  & \\
\texttt{300             }  & \\
\texttt{27 3 20         }  & \\
\texttt{5 2000 2 4      }  & \\
\texttt{300             }  & \\
\texttt{4 3 0 4         }  & \\
\texttt{450             }  & \\
\texttt{7 8 0 13        }  & \\
\end{Exemplo}

\end{Problema}


\begin{Problema}{Getting Gold}

We're building an old-school back-to-basics computer game. It's a very simple 
text based adventure game where you walk around and try to find treasure, 
avoiding falling into traps. The game is played on a rectangular grid and the 
player gets very limited information about her surroundings.

The game will consist of the player moving around on the grid for as long as 
she likes (or until she falls into a trap). The player can move up, down, left 
and right (but not diagonally). She will pick up gold if she walks into the 
same square as the gold is. If the player stands next to (i.e., immediately up, 
down, left, or right of) one or more traps, she will "sense a draft" but will 
not know from what direction the draft comes, or how many traps she's near. If 
she tries to walk into a square containing a wall, she will notice that there 
is a wall in that direction and remain in the position where she was.

For scoring purposes, we want to show the player how much gold she could have 
gotten safely. That is, how much gold can a player get playing with an optimal 
strategy and always being sure that the square she walked into was safe. The 
player does not have access to the map and the maps are randomly generated for 
each game so she has no previous knowledge of the game.


\Entrada

The first line of input contains two positive integers $W$ and $H$, neither of 
them smaller than 3 or larger than 50, giving the width and the height of the 
map, respectively. The next $H$ lines contain $W$ characters each, giving the 
map. The symbols that may occur in a map are as follows:

\begin{itemize}
  \item $P$ \-- the player's starting position
  \item $G$ \-- a piece of gold
  \item $T$ \-- a trap
  \item $\#$ \-- a wall
  \item $.$ \-- normal floor
\end{itemize}

There will be exactly one "P" in the map, and the border of the map will always 
contain walls.  \newpage


\Saida

Output the number of pieces of gold the player can get without risking falling
into a trap.

\begin{Exemplo}
\texttt{7 4                 } & \texttt{1} \\
\texttt{\#\#\#\#\#\#\#      } & \texttt{4} \\
\texttt{\#P.GTG\#           } &   \\
\texttt{\#..TGG\#           } &   \\
\texttt{\#\#\#\#\#\#\#      } &   \\
\texttt{8 6                 } &   \\
\texttt{\#\#\#\#\#\#\#\#    } &   \\
\texttt{\#...GTG\#          } &   \\
\texttt{\#..PG.G\#          } &   \\
\texttt{\#...G\#G\#         } &   \\
\texttt{\#..TG.G\#          } &   \\
\texttt{\#\#\#\#\#\#\#\#    } &   \\

\end{Exemplo}

\end{Problema}


\begin{Problema}{Aspen Avenue}

"Phew, that was the last one!" exclaimed the garden helper Tim as he threw the 
last tree plant to the ground. His employer, countess Esmeralda Hunt who owned 
the estate, has ordered him to arrange an avenue of aspen trees along both 
sides of the front road leading up to the house. The first trees in the avenue 
are supposed to be planted at the very beginning of the road, and the last 
trees of the avenue at the very end of the road. Tim, who was constantly being 
reminded of her sense of accuracy, knew that the countess would insist on the 
trees being placed in perfectly aligned tree pairs, one on each side of the 
road, and with exactly the same spacing between the pairs along the road. 
However, when bringing the tree plants to the estate, Tim had just dropped them 
arbitrarily along the left side of the road and was now facing the task of 
moving the trees to their correct positions to meet the countess’s 
requirements. Being stronger in mind than in arms, and since it was time for a 
coffee break anyway before he started digging, he sat down to figure out which 
trees to move to which positions so as to minimize the total (Euclidean) 
distance that he had to move the trees.

\Entrada

The input file starts with a positive even integer $N$ between 4 and 2000 
(inclusive), giving the total number of trees in the avenue. The next line 
contains two integers $L$ and $W$, where $1 \leq L \leq 10000$ is the length of 
the road, in meters, and $1 \leq W \leq 20$ is the width of the road, in 
meters. The next $N$ lines each describe where Tim had dropped of the trees. 
Each such line contains an integer $0 \leq p \leq L$ indicating the position of 
a tree plant along the left side of the road, measured in meters from the start 
of the road.

\Saida

For each test case, the smallest total number of meters the tree plants need to 
be moved. The answer should be given with an absolute or relative error of at 
most $10^{6}$. \\

\begin{Exemplo}
\texttt{4               } & \texttt{2.4142135624} \\
\texttt{10 1            } & \texttt{9.2853832858} \\
\texttt{1               } & \\
\texttt{0               } & \\
\texttt{10              } & \\
\texttt{10              } & \\
\texttt{6              } & \\
\texttt{10 1           } & \\
\texttt{0              } & \\
\texttt{9              } & \\
\texttt{3              } & \\
\texttt{5              } & \\
\texttt{5              } & \\
\texttt{6              } & \\
\end{Exemplo}

\end{Problema}


\begin{Problema}{Introspective Caching}

In a distributed system, data is never where you need it, and fetching data 
over a network takes time and consumes bandwidth. The problem can be mitigated 
by adding a cache, where a node stores some resources locally and if those 
resources need to be used again, it can simply take them from its cache rather 
than asking someone else for them.

However, caches have a nasty tendency to fill up, so at some point, objects 
must be evicted from the cache to make room for new objects. Choosing what 
object to remove from the cache is not easy and there are several different 
algorithms to choose from.

The marvelous Apes in Computing Machinery have come up with a fantastic new 
algorithm, the Introspective Caching Algorithm, named after a city of Peru. It 
consists of some extra hardware (a very small, precognitive monkey) which helps 
making decisions. Since the monkey can see into the future, she knows exactly 
what objects will be accessed and in what order, and using this information she 
will make optimal decisions on what objects to remove from the cache. 
Optimality here means that she will minimize the number of times an object is 
read into the cache.

All object accesses go through the cache, so every time an object is accessed, 
it must be inserted into the cache if it was not already there. All objects are 
of equal size, and no writes occur in the system, so a cached object is always 
valid. When the system starts, the cache is empty.

You have been tasked with evaluating the monkey's performance, and feeding her 
the occasional banana.

\Entrada

The first line of input contains three integers, separated by single spaces, 
telling you how many objects fit in the cache, $0 < c \leq 10000$, how many 
different objects are in the system, $c \leq n \leq 100000$, and how many 
accesses, $0 \leq a \leq 100000$, will occur. The following a lines contain a 
single integer between $0$ and $n - 1$ (inclusive) indicating what object is 
accessed. The first line corresponds to the first object accessed access and 
the last line to the last.


\Saida

Output the least number of times an object must be read into the cache to 
handle the accesses listed in the input.


\begin{Exemplo}
\texttt{1 2 3   } & \texttt{2} \\
\texttt{0       } & \texttt{5} \\
\texttt{0       } &   \\
\texttt{1       } &   \\
\texttt{3 4 8   } &   \\
\texttt{0       } &   \\
\texttt{1       } &   \\
\texttt{2       } &   \\
\texttt{3       } &   \\
\texttt{3       } &   \\
\texttt{2       } &   \\
\texttt{1       } &   \\
\texttt{0       } &   \\
\end{Exemplo}

\end{Problema}


\begin{Problema}{Code Theft}

While reviewing code recently being checked into the repository, Jim discovered 
that some employees now and then seemed to copy code right from the Internet 
into the company code base. This would be a potential disaster as the company 
then risks getting sued by copyright holders of the original code. The obvious 
solution, talking to the employees and kindly ask them not to submit any stolen 
code, seemed to solve the problem. Still, it was decided that a screening 
process should be introduced to detect newly stolen code.

The screening would work as follows: Every time new code was checked in, the 
full contents of the changed files where matched against a repository of known 
open source code. For each file the longest match, in number of consecutive 
lines, should be reported.

Comparison is done line by line. Empty lines, and lines only containing space, 
are ignored during comparison and not counted. Leading and trailing spaces 
should be ignored completely and consecutive space characters inside the lines 
are treated as one single space. The comparison is case-sensitive.

\Entrada

Test data starts with the number $0 \leq N \leq 100$ of code fragments in the repository. Then
follows, for each code fragment, one line containing the file name that the fragment was
fetched from and the contents of the fragment on subsequent lines. File names will neither
contain whitespace nor be guaranteed to be unique. The name is at most 254 characters
long. Each fragment is terminated by $***END***$ on a line by its own. This line is not
considered being part of the fragment.

After the fragments in the repository have all been listed, comes the actual code
snippet to find matches for. This snippet is also terminated by $***END***$ on a line by
its own.

Lines are guaranteed to be no longer than 254 characters. No code fragment will
be longer than 10000 lines. Any code and file name lines will only contain the ASCII
characters 32-126. The total size of the input file will not exceed 106 characters.

\Saida

For each test case, write the number of matching consecutive lines (empty lines 
not counted) in a longest match from the repository, followed by a 
space-separated list of the file names of each fragments containing a match of 
this length, given in the order that the matching fragments were presented in 
the repository description. If no fragments match, write the number 0 on a line 
of its own.


\begin{Exemplo}
\texttt{2                               } & \texttt{2 HelloWorld.c} \\
\texttt{HelloWorld.c                    } & \texttt{3 HelloWorld1.bas HelloWorld2.bas} \\
\texttt{int Main() \{                    } & \\
\texttt{    printf("Hello \%d\ n",i);    } & \\
\texttt{\}                               } & \\
\texttt{***END***                       } & \\
\texttt{Add.c                           } & \\
\texttt{int Main() \{                    } & \\
\texttt{  for (int i=0; i<10; i++)      } & \\
\texttt{    sum += i;                   } & \\
\texttt{  printf("SUM \%d", sum);       } & \\
\texttt{\}                               } & \\
\texttt{***END***                       } & \\ 
\texttt{int Main() \{                    } & \\
\texttt{  printf("Hello \%d\ n",i);      } & \\
\texttt{  printf("THE END\ n");          } & \\
\texttt{\}                               } & \\
\texttt{***END***                       } & \\
\texttt{2                                 } & \\    
\texttt{HelloWorld1.bas                     } & \\
\texttt{10 PRINT "*******************"      } & \\
\texttt{20 PRINT "*******************"      } & \\
\texttt{30 PRINT "--- HELLO WORLD ---"      } & \\
\texttt{40 PRINT "*******************"      } & \\
\texttt{50 PRINT "*******************"      } & \\
\texttt{***END***                           } & \\
\texttt{HelloWorld2.bas                     } & \\
\texttt{10 PRINT    "-------------------"   } & \\
\texttt{20 PRINT    "*******************"   } & \\
\texttt{30 PRINT    "--- HELLO WORLD ---"   } & \\
\texttt{40 PRINT    "*******************"   } & \\
\texttt{50 PRINT    "-------------------"   } & \\
\texttt{***END***                           } & \\
\texttt{10 REM Hello ver 1.0 (c) Acme 2008  } & \\
\texttt{20 PRINT "*******************"      } & \\
\texttt{30 PRINT "--- HELLO WORLD ---"      } & \\
\texttt{40 PRINT "*******************"      } & \\
\texttt{50 END                              } & \\
\texttt{***END***                           } & \\
\end{Exemplo}

\end{Problema}

